#include "definition.h"
class Solution {
 public:
  // 时间复杂度O(N),空间复杂度O(logN),后序遍历
  /*
  int countNodes(TreeNode* root) {
      if(!root) return 0;
      // int leftNum = getNodesNum(cur->left);      // 左
      // int rightNum = getNodesNum(cur->right);    // 右
      // int treeNum = leftNum + rightNum + 1;      // 中
      // return treeNum;
      return 1+countNodes(root->left)+countNodes(root->right);
  }
  */
  // 时间复杂度O(N) ，空间复杂度O(N) ，层次遍历
  /*
  int countNodes(TreeNode* root) {
      if(!root) return 0;
      queue<TreeNode*> que;
      que.push(root);
      int count = 0;
      TreeNode* temp;
      while(!que.empty()) {
          temp = que.front();
          que.pop();
          if(temp->left) que.push(temp->left);
          if(temp->right) que.push(temp->right);
          count++;
      }
      return count;
  }
  */
  // 时间复杂度O(logN*logN) ，空间复杂度O(logN) ，利用二叉树特性
  int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int leftHeight = 0,
        rightHeight = 0;  // 这里初始为0是有目的的，为了下面求指数方便
    while (left) {  // 求左子树深度
      left = left->left;
      leftHeight++;
    }
    while (right) {  // 求右子树深度
      right = right->right;
      rightHeight++;
    }
    if (leftHeight == rightHeight) {
      return (2 << leftHeight) -
             1;  // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
  }
};